package week_03;

import java.util.*;

/**
 * 示例 1:
 * <p>
 * 输入: 2, [[1,0]]
 * 输出: [0,1]
 * 解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
 * 示例 2:
 * <p>
 * 输入: 4, [[1,0],[2,0],[3,1],[3,2]]
 * 输出: [0,1,2,3] or [0,2,1,3]
 * 解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
 *      因此，一个正确的课程顺序是[0,1,2,3] 。另一个正确的排序是[0,2,1,3] 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/course-schedule-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 **/
public class CoursesCanFinish2_210 {
    private int n;
    private int m;
    private int[][] prerequisites;
    private List<List<Integer>> edges;
    private int[] indegs;
    private int[] orders;


    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //  使用广度优先 搜索 每个点广度搜索一遍
        //  每个点计算一个入度，出一个点则将下一个点的入度减1
        //建图 加边 建立入度数组
        n = numCourses;

        prerequisites = prerequisites;
        orders = new int[n];
        edges = new ArrayList<>();
        indegs = new int[n];
        for (int i = 0; i < n; i++) {
            edges.add(new ArrayList<>());
        }
        for (int[] item : prerequisites) {
            int u = item[0];
            int v = item[1];
            addEdge(u, v);
        }
        m=0;
        // 拓扑排序计算
        topSort();
        if (m == n) return orders;
        return new int[]{};
    }

    public void topSort() {
        Deque<Integer> queue = new LinkedList<>();
        // 0度入队列
        for (int i = 0; i < n; i++) {
            if (indegs[i] == 0) queue.offer(i);
        }
        // topSort
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            orders[m] = cur;
            m++;
            for (int e : edges.get(cur)) {
                indegs[e] -= 1;
                if (indegs[e] == 0) {
                    queue.offer(e);
                }
            }
        }
    }

    public void addEdge(int u, int v) {
        edges.get(u).add(v);
        System.out.println(u + ":" + v);
        indegs[v] += 1;
    }
}
